package 滑动窗口

/*
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

	请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
*/
func lengthOfLongestSubstring(s string) int {
	m := map[byte]int{} // 哈希集合，记录每个字符是否出现过
	n := len(s)

	// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
	right, res := -1, 0
	for i := 0; i < n; i++ { //遍历字符串
		if i != 0 {
			delete(m, s[i-1]) // 左指针向右移动一格，移除一个字符
		}

		for right+1 < n && m[s[right+1]] == 0 { //如果右指针下个位置还没有超边界 && 下个位置元素没有再map中出现
			m[s[right+1]]++ // 给下个元素再map中值+1
			right++         //右指针++
		}

		//更新结果
		res = max(res, right-i+1) // 第 i 到 right 个字符是一个极长的无重复字符子串
	}
	return res
}

func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
